package com.wesley.growth.algorithms.sort;

/**
 * 插入排序, 特点是提前终止内层循环
 * @author Wesley Created By 2018/8/13
 */
public class InsertionSort extends AbstractSort{

    @Override
    public void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++){
            // 减少赋值次数,提高效率
            int e = arr[i];
            // j 代表抓到的牌，先放到最右侧，不断交换到对应的位置
            int j;
            for(j = i; j > 0 && arr[j-1] > e; j --){
                arr[j] = arr[j-1];
            }
            arr[j] = e;
        }
    }

}
